import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class QuickSort2 {
    public static void main(String[] args) {
        int[] arr = { 5, 3, 8, 4, 2, 7, 1, 6 };
        System.out.println("before sort: " + Arrays.toString(arr));
        System.out.println("after sort: " + Arrays.toString(quickSort(arr)));
    }

    public static int[] quickSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }
        int pivot = arr[0];
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < pivot) {
                left.add(arr[i]);
            } else {
                right.add(arr[i]);
            }
        }
        int[] sortedLeft = quickSort(left.stream().mapToInt(i -> i).toArray());
        int[] sortedRight = quickSort(right.stream().mapToInt(i -> i).toArray());
        List<Integer> result = new ArrayList<>();
        result.addAll(Arrays.stream(sortedLeft).boxed().collect(Collectors.toList()));
        result.add(pivot);
        result.addAll(Arrays.stream(sortedRight).boxed().collect(Collectors.toList()));
        return result.stream().mapToInt(i -> i).toArray();
    }
}
